Recursion ========= A recursive method is a method that calls itself, either directly or indirectly. Why are recursive methods useful? 1. Many data structures are recursive in nature E.g., file system folders (folders contain folders, etc.), arithmetic expressions (expression may be the sum of two expressions, etc.), dictionary (words defined in terms of other words) 2. Some algorithms are most easily expressed with recursion E.g., inductive decision tree learning, arithmetic expression handling, etc. 3. Recursion is fun! A Simple Exercise ----------------- Write a non-recursive program that takes two integers, x and n, as inputs and computes x to the power of n int power (int x, int n) { int result = 1; for (int i = 0; i < n; i++) result *= x; return result; } Write the same program using recursion: Getting started: int power (int x, int n) { return x * power (x, n-1); } See Power1.java What is the problem? Infinite recursion (like infinite loop) How do we make it stop? Where should it stop? What's the smallest integer power we can compute this way? A number raised to the power 0 is 1 Modify program: int power (int x, int n) { if (n == 0) return 1; else return x * power (x, n-1); } See Power2.java The "termination condition" for a recursive method is known as its base case. The base case is the (smallest) instance that can be solved without recursion. FIRST RULE OF RECURSION: A recursive method must have a base case What happens when we run our program with a negative value of n? Run Power2 with inputs 2 and -3 for example What is the problem? SECOND RULE OF RECURSION: Recursive calls must progress toward the base case Another Exercise ---------------- Here is a method that performs what is known as a binary search: int fSearch( int [ ] a, int x ) { int low = 0; int high = a.length - 1; int mid; while( low <= high ) { mid = ( low + high ) / 2; if( x > a[ mid ] ) low = mid + 1; else if( x < a[ mid ] ) high = mid - 1; else return mid; } return NOT_FOUND; // NOT_FOUND = -1 } Write the recursive version of this algorithm. int recBinarySearch( Comparable[] a, Comparable x, int low, int high ) { if( low > high ) return NOT_FOUND; int mid = ( low + high ) / 2; if( a[ mid ].compareTo( x ) < 0 ) return recBinarySearch( a, x, mid + 1, high ); else if( a[ mid ].compareTo( x ) > 0 ) return recBinarySearch( a, x, low, mid - 1 ); else return mid; } Making Sure It Works -------------------- How can you feel confident that a recursive method works correctly? Use the principle of induction: 1. Show it works correctly for the base case 2. Show that if it works correctly for "k" then it works correctly for "k+1" (where "k" is the subject of the recursion) Checking the power method: 1. Base case: If n=0 then no recursive call is made and line 3 correctly outputs 1 2. Inductive step: Assume that power works correctly for all n>=1. Show that it works correctly for n+1. Since n<>0, the if statement at line 2 is not satisfied and the recursive call at line 5 is executed. By the inductive hypothesis, that call returns x^n, which is then multiplied by x, yielding the correct result x^(n+1) THIRD RULE OF RECURSION: Assume that the recursive call works Understanding How It Works -------------------------- What happens when we run the power method with a large power? See Power2.java Stack overflow How does the system implement recursion? Stack of activation records Stores space for parameters and local variables Why is a stack a good fit for this problem? Methods return in reverse order of calls Method call: push activation record Method return: pop activation record A small exercise Give the stack contents for recBinarySearch, with a: 4 7 13 19 25 27 41 52 57 63 x: 52 low: 1 high: 10 Yet Another Example ------------------- Suppose you need to compute the nth Fibonacci number: Fibonacci series: 1 1 2 3 5 8 13 21 34 55 89 Rule: next number is sum of previous two numbers Intuition: number of rabbits after n months How do you get the nth number based on previous numbers? fib(n) = fib(n-1) + fib(n-2) What is the base case? fib(1) = 1 With only one base case, however, we have a problem when trying to compute fib(2) = fib(1) + fib(0). How do we solve this problem? Add a second base case fib(2) = 1 How do we put this all together into a recursive method? int fib (int n) { if (n <= 2) return 1; else return fib(n-1) + fib(n-2); } (a) Fib1.java How long does it take to compute fib(10)? How long does it take to compute fib(30)? How long does it take to compute fib(40)? How long does it take to compute fib(41)? How long does it take to compute fib(42)? How long does it take to compute fib(43)? How many adds are needed to get fib(10)? How many adds are needed to get fib(30)? How many adds are needed to get fib(40)? So, why does the recursive method take so long? (b) Fib2.java Redundant computation fib(n) computes fib(n-1) and fib(n-2) fib(n-1) computes fib(n-2) again, etc. What is the number, c(n), of calls to fib needed to compute fib(n)? - c(0) = c(1) = 1 - c(n) = c(n-1) + c(n-2) + 1 - show by induction that, for n >= 3, c(n) = fib(n+2) + fib(n-1) - 1 Running time is exponential FOURTH RULE OF RECURSION: Never solve the same problem instance more than once Ecercise: Design a solution to fib(n) whose running time is linear (c) Fib-It.java Recursion vs. Iteration ----------------------- Power can be implemented using recursion or iteration (i.e., a loop) - Which is the better way to write power? - How do you choose between using recursion or iteration? - Does recursion really help or does it just make things more confusing? Things to consider: Each recursive call has some overhead The number of nested recursive calls is limited by stack size Recursion gives simpler solution to some problems So how about power(x, n) and fib(n) for example? Iteration probably better Some More Exercises ------------------- 1. Write a recursive program that computes GCD(X,Y) GCD(X,Y) is the largest D that divides both X and Y One can prove that: GCD(X,Y) = GCD(X-Y,Y) GCD(X,Y) = GCD(Y,X mod Y) (a) Gcd.java 2. Write a recursive program that finds the largest element in an array of n elements. (b) FindLargest.java 3. Write a recursive program that prints all the permutations of an arbitrary input string e.g., ABC produces ABC, ACB, BAC, BCA, CAB, and CBA (c) Perm.java